#ifndef __CPPBTREE_H
#define __CPPBTREE_H
#include <cmath>
#include <iostream>
#include <cstdlib>
#define ElementType void*
//比较大小或相等的枚举体
enum sign
{
    bigger=1,
    smaller,
    equal
};


class BinaryTreeNode
{
public:
    BinaryTreeNode(ElementType element);
    ~BinaryTreeNode();
    friend class BinarySortTree; //友元类
    ElementType GetNodeData();
    bool IsLeftChild(BinaryTreeNode* parent,BinaryTreeNode* child);
    BinaryTreeNode* RemoveByElement(BinaryTreeNode* node,ElementType element,int(*funcptr)(ElementType,ElementType));
private:
    ElementType data; //数据域
    BinaryTreeNode* Left;     //左孩子
    BinaryTreeNode* Right;      //右孩子
    BinaryTreeNode* parent;     //双亲

    BinaryTreeNode* RotateLeft(); //左旋
    BinaryTreeNode* RotateRight(); //右旋
    BinaryTreeNode* Rotate_LeftRight(); //左右旋
    BinaryTreeNode* Rotate_RightLeft(); //右左旋
    BinaryTreeNode* InsertNode(BinaryTreeNode* node, ElementType element,int(*funcptr)(ElementType,ElementType)); //
    int GetNodeHeight();
    void TravelPrev_Node(void(*funcptr)(ElementType));
    void TravelMid_Node(void(*funcptr)(ElementType));
    void TravelPost_Node(void(*funcptr)(ElementType));
    BinaryTreeNode* SearchNode(ElementType element,int(*funcptr)(ElementType,ElementType));
};
using BTNode = BinaryTreeNode;


class BinarySortTree
{
public:
    BinarySortTree();
    friend class BinaryTreeNode;
    BTNode* InsertElement_BSTree(ElementType element,int(*funcptr)(ElementType,ElementType));
    void TravelPrev_BSTree(void(*funcptr)(ElementType)); //前序遍历
    void TravelMid_BSTree(void(*funcptr)(ElementType)); //中序遍历
    void TravelPost_BSTree(void(*funcptr)(ElementType)); //后序遍历
    BTNode* SearchByElement_BTNode(ElementType element,int(*funcptr)(ElementType,ElementType)); //按值查找
    BinaryTreeNode* RemoveByElement(BinaryTreeNode* node,ElementType element,int(*funcptr)(ElementType,ElementType));//删除一个结点
    BinaryTreeNode* GetTreeRoot();
private:
    BTNode* root;
    
};
using BSTree = BinarySortTree;



#endif